package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSameTree1(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if p == nil || q == nil {
		return false
	}

	return p.Val == q.Val && isSameTree1(p.Left, q.Left) && isSameTree1(p.Right, q.Right)
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if p == nil || q == nil {
		return false
	}

	pS, qS := make([]*TreeNode, 1, 8), make([]*TreeNode, 1, 8)
	pL, qL := 1, 1
	pS[0], qS[0] = p, q
	for pL > 0 && qL > 0 {
		pg, qg := pS[pL-1], qS[qL-1]
		pL--
		qL--
		if pg == nil && qg == nil {
			continue
		}

		if pg == nil || qg == nil || pg.Val != qg.Val {
			return false
		}

		pS = append(pS[:pL], pg.Left, pg.Right)
		qS = append(qS[:qL], qg.Left, qg.Right)
		pL, qL = pL+2, qL+2
	}

	return pL == qL
}
